home *** CD-ROM | disk | FTP | other *** search
/ Day Cry / Day Cry CD.bin / oh_towns / taropyon / splib / splib.lzh / PRG / LHX / DHUF.C < prev    next >
C/C++ Source or Header  |  1993-11-11  |  6KB  |  374 lines
  1. /**************************************************************
  2.         title    dhuf.c
  3. ***************************************************************
  4.     Dynamic Huffman routine
  5.                                                 H.Yoshizaki
  6. **************************************************************/
  7. #include    "lh386.h"
  8.  
  9. #include    <stdio.h>
  10. #include    "slidehuf.h"
  11.  
  12. #ifdef    __HIGHC__
  13. #    pragma    On(Align_labels);
  14. #endif
  15.  
  16. #ifdef    __HIGHC__
  17. #    ifndef    PASCAL
  18. #        define    PASCAL    (_DEFAULT_CALLING_CONVENTION | _CALLEE_POPS_STACK)
  19. #    endif
  20. #endif
  21.  
  22. #ifdef    __HIGHC__
  23. #    pragma    Calling_convention(PASCAL);
  24. #endif
  25. static void start_p_dyn(void);
  26. static void reconst(int start, int end);
  27. static int    swap_inc(int p);
  28. static void update_c(int p);
  29. static void update_p(int p);
  30. static void make_new_node(int p);
  31. static void encode_c_dyn(int c);
  32. #ifdef    __HIGHC__
  33. #    pragma    Calling_convention();
  34. #endif
  35.  
  36.  
  37. #define N_CHAR        (256 + 60 - THRESHOLD + 1)
  38. #define TREESIZE_C    (N_CHAR * 2)
  39. #define TREESIZE_P    (128 * 2)
  40. #define TREESIZE    (TREESIZE_C + TREESIZE_P)
  41. #define ROOT_C        0
  42. #define ROOT_P        TREESIZE_C
  43.  
  44. uint        n_max;
  45.  
  46. static short child[TREESIZE], parent[TREESIZE], block[TREESIZE], edge[TREESIZE], stock[TREESIZE], node[TREESIZE / 2];
  47.  
  48. static unsigned short freq[TREESIZE];
  49.  
  50. static unsigned short total_p;
  51. static int    avail, n1;
  52. static int    most_p, nn;
  53. static unsigned long nextcount;
  54.  
  55. void        start_c_dyn(void)
  56. {
  57.     int         i, j, f;
  58.  
  59.     n1 = (n_max >= 256 + maxmatch - THRESHOLD + 1) ? 512 : n_max - 1;
  60.     for (i = 0; i < TREESIZE_C; i++)
  61.     {
  62.         stock[i] = i;
  63.         block[i] = 0;
  64.     }
  65.     for (i = 0, j = n_max * 2 - 2; i < n_max; i++, j--)
  66.     {
  67.         freq[j] = 1;
  68.         child[j] = ~i;
  69.         node[i] = j;
  70.         block[j] = 1;
  71.     }
  72.     avail = 2;
  73.     edge[1] = n_max - 1;
  74.     i = n_max * 2 - 2;
  75.     while (j >= 0)
  76.     {
  77.         f = freq[j] = freq[i] + freq[i - 1];
  78.         child[j] = i;
  79.         parent[i] = parent[i - 1] = j;
  80.         if (f == freq[j + 1])
  81.         {
  82.             edge[block[j] = block[j + 1]] = j;
  83.         } else
  84.         {
  85.             edge[block[j] = stock[avail++]] = j;
  86.         }
  87.         i -= 2;
  88.         j--;
  89.     }
  90. }
  91.  
  92. static void start_p_dyn(void)
  93. {
  94.     freq[ROOT_P] = 1;
  95.     child[ROOT_P] = ~(N_CHAR);
  96.     node[N_CHAR] = ROOT_P;
  97.     edge[block[ROOT_P] = stock[avail++]] = ROOT_P;
  98.     most_p = ROOT_P;
  99.     total_p = 0;
  100.     nn = 1 << dicbit;
  101.     nextcount = 64;
  102. }
  103.  
  104. void        decode_start_dyn(void)
  105. {
  106.     n_max = 286;
  107.     maxmatch = MAXMATCH;
  108.     init_getbits();
  109.     start_c_dyn();
  110.     start_p_dyn();
  111. }
  112.  
  113. static void reconst(int start, int end)
  114. {
  115.     int         i, j, k, l, b;
  116.     unsigned short f, g;
  117.  
  118.     for (i = j = start; i < end; i++)
  119.     {
  120.         if ((k = child[i]) < 0)
  121.         {
  122.             freq[j] = (freq[i] + 1) / 2;
  123.             child[j] = k;
  124.             j++;
  125.         }
  126.         if (edge[b = block[i]] == i)
  127.         {
  128.             stock[--avail] = b;
  129.         }
  130.     }
  131.     j--;
  132.     i = end - 1;
  133.     l = end - 2;
  134.     while (i >= start)
  135.     {
  136.         while (i >= l)
  137.         {
  138.             freq[i] = freq[j];
  139.             child[i] = child[j];
  140.             i--, j--;
  141.         }
  142.         f = freq[l] + freq[l + 1];
  143.         for (k = start; f < freq[k]; k++);
  144.         while (j >= k)
  145.         {
  146.             freq[i] = freq[j];
  147.             child[i] = child[j];
  148.             i--, j--;
  149.         }
  150.         freq[i] = f;
  151.         child[i] = l + 1;
  152.         i--;
  153.         l -= 2;
  154.     }
  155.     f = 0;
  156.     for (i = start; i < end; i++)
  157.     {
  158.         if ((j = child[i]) < 0)
  159.             node[~j] = i;
  160.         else
  161.             parent[j] = parent[j - 1] = i;
  162.         if ((g = freq[i]) == f)
  163.         {
  164.             block[i] = b;
  165.         } else
  166.         {
  167.             edge[b = block[i] = stock[avail++]] = i;
  168.             f = g;
  169.         }
  170.     }
  171. }
  172.  
  173. static int    swap_inc(int p)
  174. {
  175.     int         b, q, r, s;
  176.  
  177.     b = block[p];
  178.     if ((q = edge[b]) != p)
  179.     {                            /* swap for leader */
  180.         r = child[p];
  181.         s = child[q];
  182.         child[p] = s;
  183.         child[q] = r;
  184.         if (r >= 0)
  185.             parent[r] = parent[r - 1] = q;
  186.         else
  187.             node[~r] = q;
  188.         if (s >= 0)
  189.             parent[s] = parent[s - 1] = p;
  190.         else
  191.             node[~s] = p;
  192.         p = q;
  193.         goto Adjust;
  194.     } else if (b == block[p + 1])
  195.     {
  196.       Adjust:
  197.         edge[b]++;
  198.         if (++freq[p] == freq[p - 1])
  199.         {
  200.             block[p] = block[p - 1];
  201.         } else
  202.         {
  203.             edge[block[p] = stock[avail++]] = p;        /* create block */
  204.         }
  205.     } else if (++freq[p] == freq[p - 1])
  206.     {
  207.         stock[--avail] = b;     /* delete block */
  208.         block[p] = block[p - 1];
  209.     }
  210.     return parent[p];
  211. }
  212.  
  213. static void update_c(int p)
  214. {
  215.     int         q;
  216.  
  217.     if (freq[ROOT_C] == 0x8000)
  218.     {
  219.         reconst(0, n_max * 2 - 1);
  220.     }
  221.     freq[ROOT_C]++;
  222.     q = node[p];
  223.     do
  224.     {
  225.         q = swap_inc(q);
  226.     } while (q != ROOT_C);
  227. }
  228.  
  229. static void update_p(int p)
  230. {
  231.     int         q;
  232.  
  233.     if (total_p == 0x8000)
  234.     {
  235.         reconst(ROOT_P, most_p + 1);
  236.         total_p = freq[ROOT_P];
  237.         freq[ROOT_P] = 0xffff;
  238.     }
  239.     q = node[p + N_CHAR];
  240.     while (q != ROOT_P)
  241.     {
  242.         q = swap_inc(q);
  243.     }
  244.     total_p++;
  245. }
  246.  
  247. static void make_new_node(int p)
  248. {
  249.     int         q, r;
  250.  
  251.     r = most_p + 1;
  252.     q = r + 1;
  253.     node[~(child[r] = child[most_p])] = r;
  254.     child[q] = ~(p + N_CHAR);
  255.     child[most_p] = q;
  256.     freq[r] = freq[most_p];
  257.     freq[q] = 0;
  258.     block[r] = block[most_p];
  259.     if (most_p == ROOT_P)
  260.     {
  261.         freq[ROOT_P] = 0xffff;
  262.         edge[block[ROOT_P]]++;
  263.     }
  264.     parent[r] = parent[q] = most_p;
  265.     edge[block[q] = stock[avail++]] = node[p + N_CHAR] = most_p = q;
  266.     update_p(p);
  267. }
  268.  
  269. static void encode_c_dyn(int c)
  270. {
  271.     unsigned short bits;
  272.     int         p, d, cnt;
  273.  
  274.     d = c - n1;
  275.     if (d >= 0)
  276.     {
  277.         c = n1;
  278.     }
  279.     cnt = bits = 0;
  280.     p = node[c];
  281.     do
  282.     {
  283.         bits >>= 1;
  284.         if (p & 1)
  285.         {
  286.             bits |= 0x8000;
  287.         }
  288.         if (++cnt == 16)
  289.         {
  290.             putcode(16, bits);
  291.             cnt = bits = 0;
  292.         }
  293.     } while ((p = parent[p]) != ROOT_C);
  294.     putcode(cnt, bits);
  295.     if (d >= 0)
  296.         putbits(8, d);
  297.     update_c(c);
  298. }
  299.  
  300. ushort        decode_c_dyn(void)
  301. {
  302.     int         c;
  303.     short        buf, cnt;
  304.  
  305.     c = child[ROOT_C];
  306.     buf = bitbuf;
  307.     cnt = 0;
  308.     do
  309.     {
  310.         c = child[c - (buf < 0)];
  311.         buf <<= 1;
  312.         if (++cnt == 16)
  313.         {
  314.             fillbuf(16);
  315.             buf = bitbuf;
  316.             cnt = 0;
  317.         }
  318.     } while (c > 0);
  319.     fillbuf(cnt);
  320.     c = ~c;
  321.     update_c(c);
  322.     if (c == n1)
  323.         c += getbits(8);
  324.     return c;
  325. }
  326.  
  327. ushort        decode_p_dyn(void)
  328. {
  329.     int         c;
  330.     short        buf, cnt;
  331.  
  332.     while (count > nextcount)
  333.     {
  334.         make_new_node(nextcount / 64);
  335.         if ((nextcount += 64) >= nn)
  336.             nextcount = 0xfffffffful;
  337.     }
  338.     c = child[ROOT_P];
  339.     buf = bitbuf;
  340.     cnt = 0;
  341.     while (c > 0)
  342.     {
  343.         c = child[c - (buf < 0)];
  344.         buf <<= 1;
  345.         if (++cnt == 16)
  346.         {
  347.             fillbuf(16);
  348.             buf = bitbuf;
  349.             cnt = 0;
  350.         }
  351.     }
  352.     fillbuf(cnt);
  353.     c = (~c) - N_CHAR;
  354.     update_p(c);
  355.  
  356.     /* ë║ê╩éUârâbâgé≡é╗é╠é▄é▄ôⁿù═é╖éΘüB */
  357.     return (c << 6) + getbits(6);
  358. }
  359.  
  360. void        output_dyn(int code, unsigned int pos)
  361. {
  362.     encode_c_dyn(code);
  363.     if (code >= 0x100)
  364.     {
  365.         encode_p_st0(pos);
  366.     }
  367. }
  368.  
  369. void        encode_end_dyn(void)
  370. {
  371.     putcode(7, 0);
  372. }
  373.  
  374.